#ifndef ARRAY
#define ARRAY

#include "ReversedIterator.cpp"

template<typename TValue>
class Array
{
private:
	// 默认容量使得内部申请的数组为4096字节
	static constexpr int DefaultLength = 4096 / sizeof(TValue);
	static constexpr int DefaultCapacity = DefaultLength - 2;
public:
	using ExceptionType = int;
	using ValueType = TValue;
	static constexpr ExceptionType OutOfRange = -1;
public:
	// 构造一个具有指定初始容量的Array
	Array(int initCapacity = DefaultCapacity);
	// 使用一个范围进行构造，包括begin但不包括end
	template<typename TIterator>
	Array(TIterator beginIt, TIterator endIt, int initCapacity = DefaultCapacity);
	// 析构
	~Array();
	// 复制
	Array(Array& other);
	// 移动
	Array(Array&& other);
	// 赋值
	Array& operator=(Array& other);
	Array& operator=(Array&& other);

	class ArrayIterator;
	using ReversedArrayIterator = ReversedRandomAccessIterator<ArrayIterator>;
	class ArrayIterator
	{
	public:
		using ValueType = TValue;
		// 前置++
		ArrayIterator& operator++() noexcept;
		// 前置--
		ArrayIterator& operator--() noexcept;
		// 随机访问
		ArrayIterator operator+(int offset) noexcept;
		ArrayIterator operator-(int offset) noexcept;
		bool operator==(const ArrayIterator& other) const noexcept;
		bool operator!=(const ArrayIterator& other) const noexcept;
		TValue& operator*();
		TValue* operator->();
		operator ReversedArrayIterator();
		ArrayIterator(ReversedArrayIterator& rIt);
	private:
		friend class Array;
		ArrayIterator(TValue* pValue);
		TValue* pValue;
	};

public:
	// 直接随机访问, 索引从0开始
	TValue& operator[](int index);
	// 获取迭代器
	ArrayIterator Begin();
	ArrayIterator End();
	ReversedArrayIterator ReversedBegin();
	ReversedArrayIterator ReversedEnd();
	// 在it之前插入value, 并且返回指向插入的值的iterator
	ArrayIterator Insert(const TValue& value, ArrayIterator&& it);
	ArrayIterator Insert(const TValue& value, ArrayIterator& it);
	// 在最后插入
	ArrayIterator InsertBack(const TValue& value);
	// 在开头插入
	ArrayIterator InsertFront(const TValue& value);
	// 移除it, 并且返回it原先的后继iterator
	ArrayIterator Remove(ArrayIterator&& it);
	ArrayIterator Remove(ArrayIterator& it);
	// 删除所有某个元素， 返回删除的个数
	template<typename TComparator>
	int RemoveAll(const TValue& value, TComparator compare);
	// 查找value, 并且返回指向value的iterator, 如果找不到则返回End()
	template<typename TComparator>
	ArrayIterator Find(const TValue value, TComparator compare);
	// 将容量缩减至当前元素个数
	void Shrink();
	// 获取实际存储的元素个数
	int Count();
private:
	TValue* pArray;
	int capacity; // 容量等于pArray的长度-2
	int count;
	int beginIndex;
	int endIndex;
};

template<typename TValue>
Array<TValue>::Array(int initCapacity)
{
	this->capacity = initCapacity;
	this->pArray = new TValue[initCapacity + 2];
	this->beginIndex = this->capacity / 4;
	this->endIndex = this->beginIndex + 1;
	this->count = 0;
}

template<typename TValue>
template<typename TIterator>
Array<TValue>::Array(TIterator beginIt, TIterator endIt, int initCapacity)
{
	this->capacity = initCapacity;
	this->pArray = new TValue[initCapacity + 2];
	this->beginIndex = this->capacity / 4;
	this->endIndex = this->beginIndex + 1;
	this->count = 0;
	for (auto it = beginIt; it != endIt; ++it)
	{
		this->InsertBack(*it);
	}
}


template<typename TValue>
Array<TValue>::~Array()
{
	delete[] this->pArray;
}

template<typename TValue>
Array<TValue>::Array(Array& other)
{
	this->capacity = other.capacity;
	this->count = other.count;
	this->pArray = new TValue[this->capacity + 2];
	this->beginIndex = other.beginIndex;
	this->endIndex = other.endIndex;
	for (int i = this->beginIndex; i <= this->endIndex; ++i)
	{
		this->pArray[i] = other.pArray[i];
	}
}

template<typename TValue>
Array<TValue>::Array(Array&& other)
{
	this->capacity = other.capacity;
	this->count = other.count;
	this->pArray = other.pArray;
	this->beginIndex = other.beginIndex;
	this->endIndex = other.endIndex;
	other.pArray = nullptr;
}

template<typename TValue>
Array<TValue>& Array<TValue>::operator=(Array& other)
{
	delete[] this->pArray;
	this->capacity = other.capacity;
	this->count = other.count;
	this->pArray = new TValue[this->capacity + 2];
	this->beginIndex = other.beginIndex;
	this->endIndex = other.endIndex;
	for (int i = this->beginIndex; i <= this->endIndex; ++i)
	{
		this->pArray[i] = other.pArray[i];
	}
	return *this;
}

template<typename TValue>
Array<TValue>& Array<TValue>::operator=(Array&& other)
{
	delete[] this->pArray;
	this->capacity = other.capacity;
	this->count = other.count;
	this->pArray = other.pArray;
	other.pArray = nullptr;
	this->beginIndex = other.beginIndex;
	this->endIndex = other.endIndex;
	return *this;
}

template<typename TValue>
TValue& Array<TValue>::operator[](int index)
{
	if (index < 0 || index >= this->count)
	{
		throw Array::OutOfRange;
	}
	return this->pArray[this->beginIndex + index + 1];
}

template<typename TValue>
typename Array<TValue>::ArrayIterator Array<TValue>::Begin()
{
	return ArrayIterator(this->pArray + this->beginIndex + 1);
}

template<typename TValue>
typename Array<TValue>::ArrayIterator Array<TValue>::End()
{
	return ArrayIterator(this->pArray + this->endIndex);
}

template<typename TValue>
typename Array<TValue>::ReversedArrayIterator Array<TValue>::ReversedBegin()
{
	ArrayIterator rbegin(this->pArray + this->endIndex - 1);
	return ReversedArrayIterator(rbegin);
}

template<typename TValue>
typename Array<TValue>::ReversedArrayIterator Array<TValue>::ReversedEnd()
{
	ArrayIterator rend(this->pArray + this->beginIndex);
	return ReversedArrayIterator(rend);
}

template<typename TValue>
typename Array<TValue>::ArrayIterator Array<TValue>::Insert(const TValue& value, ArrayIterator&& it)
{
	return this->Insert(value, it);
}

template<typename TValue>
typename Array<TValue>::ArrayIterator Array<TValue>::Insert(const TValue& value, ArrayIterator& it)
{
	if (it == this->End())
	{
		return this->InsertBack(value);
	}
	else if (it == this->Begin())
	{
		return this->InsertFront(value);
	}
	// 往中间插入，计算it距离哪头近，就移动那边元素
	int insertIndex = it.pValue - this->pArray;
	int direction = 1; // 1表示移动右边
	if (insertIndex - this->beginIndex <= this->endIndex - insertIndex)
	{
		direction = 0; // 0表示移动左边
	}

	// 待移动的方向到达了边界，则触发扩展，这时要复制所有元素，因此行为是一致的
	if ((direction == 1 && this->endIndex == this->capacity + 1) || (direction == 0 && this->beginIndex == 0))
	{
		// 复制到插入位置之前，然后加入新元素，再继续复制
		int newCapacity = this->capacity + DefaultLength;
		TValue* pNewArray = new TValue[newCapacity + 2];
		// 如果是向左扩展，则元素从新数组的DefaultLength - 2索引开始存放，否则从原先的索引开始进行存放
		int newBeginIndex = this->beginIndex;
		if (direction == 0)
		{
			newBeginIndex = DefaultLength - 2;
		}
		int idx = newBeginIndex + 1;
		auto i = this->Begin();
		auto end = this->End();
		for (; i != it; ++i)
		{
			pNewArray[idx] = *i;
			++idx;
		}
		pNewArray[idx] = value;
		auto pos = pNewArray + idx;
		++idx;
		while (i != end)
		{
			pNewArray[idx] = *i;
			++i;
			++idx;
		}
		delete[] this->pArray;
		this->pArray = pNewArray;
		this->capacity = newCapacity;
		this->count++;
		this->beginIndex = newBeginIndex;
		this->endIndex = newBeginIndex + this->count + 1;
		return ArrayIterator(pos);
	}
	// 不需要扩展，仅移动元素
	else if (direction == 1)
	{
		// 向右移动
		auto fastIt = this->End() - 1;
		auto slowIt = this->End();
		while (slowIt != it)
		{
			*slowIt = *fastIt;
			--slowIt;
			--fastIt;
		}
		*slowIt = value;
		this->count++;
		this->endIndex++;
		return slowIt;
	}
	else if (direction == 0)
	{
		// 向左移动
		auto fastIt = this->Begin();
		auto slowIt = this->Begin() - 1;
		while (slowIt != it)
		{
			*slowIt = *fastIt;
			++slowIt;
			++fastIt;
		}
		*slowIt = value;
		this->count++;
		this->beginIndex--;
		return slowIt;
	}
	else
	{

	}
}

template<typename TValue>
typename Array<TValue>::ArrayIterator Array<TValue>::InsertBack(const TValue& value)
{
	// 右侧到头，触发扩展
	if (this->endIndex == this->capacity + 1)
	{
		TValue* pNewArray = new TValue[this->capacity + 2 + DefaultLength];
		for (int i = this->beginIndex + 1; i < this->endIndex; ++i)
		{
			pNewArray[i] = this->pArray[i];
		}
		delete this->pArray;
		this->pArray = pNewArray;
		this->capacity += DefaultLength;
	}
	this->pArray[this->endIndex] = value;
	this->count += 1;
	this->endIndex += 1;
	return ArrayIterator(this->pArray + this->endIndex - 1);
}

template<typename TValue>
typename Array<TValue>::ArrayIterator Array<TValue>::InsertFront(const TValue& value)
{
	// 左侧到头，触发扩展
	if (this->beginIndex == 0)
	{
		TValue* pNewArray = new TValue[this->capacity + 2 + DefaultLength];
		for (int i = this->beginIndex + 1; i < this->endIndex; ++i)
		{
			pNewArray[i + DefaultLength] = this->pArray[i];
		}
		delete this->pArray;
		this->pArray = pNewArray;
		this->capacity += DefaultLength;
		this->beginIndex += DefaultLength;
	}
	this->pArray[this->beginIndex] = value;
	this->count += 1;
	this->beginIndex -= 1;
	return ArrayIterator(this->pArray + this->beginIndex + 1);
}

template<typename TValue>
typename Array<TValue>::ArrayIterator Array<TValue>::Remove(ArrayIterator&& it)
{
	return this->Remove(it);
}

template<typename TValue>
typename Array<TValue>::ArrayIterator Array<TValue>::Remove(ArrayIterator& it)
{
	int direction = 1; // 1表示移动右边
	auto originPos = it.pValue; // 如果移动右边，则原先的位置就变成后继
	int insertIndex = it.pValue - this->pArray;
	if (insertIndex - this->beginIndex <= this->endIndex - insertIndex)
	{
		direction = 0; // 0表示移动左边
		++originPos;
	}
	if (direction == 1)
	{
		auto slowIt = it;
		auto fastIt = slowIt + 1;
		auto endIt = this->End();
		while (fastIt != endIt)
		{
			*slowIt = *fastIt;
			++slowIt;
			++fastIt;
		}
		this->count--;
		this->endIndex--;
	}
	else
	{
		auto slowIt = ReversedArrayIterator(it);
		auto fastIt = slowIt + 1;
		auto endIt = this->ReversedEnd();
		while (fastIt != endIt)
		{
			*slowIt = *fastIt;
			++slowIt;
			++fastIt;
		}
		this->count--;
		this->beginIndex++;
	}
	return ArrayIterator(originPos);
}

template<typename TValue>
template<typename TComparator>
int Array<TValue>::RemoveAll(const TValue& value, TComparator compare)
{
	int numToRemove = 0;
	int* indexToRemove = new int[this->count];
	for (int i = this->beginIndex + 1; i < this->endIndex; ++i)
	{
		if (compare(value, this->pArray[i]) == 0)
		{
			indexToRemove[numToRemove] = i;
			++numToRemove;
		}
	}
	if (numToRemove == 0)
	{
		delete[] indexToRemove;
		return 0;
	}
	int removed = 0;
	for (int i = indexToRemove[0]; i <= this->endIndex - 1 - numToRemove; ++i)
	{
		while (i + removed == indexToRemove[removed] && removed < numToRemove)
		{
			++removed;
		}
		this->pArray[i] = this->pArray[i + removed];
	}

	delete[] indexToRemove;
	this->count -= numToRemove;
	this->endIndex -= numToRemove;
	return numToRemove;
}

template<typename TValue>
template<typename TComparator>
typename Array<TValue>::ArrayIterator Array<TValue>::Find(const TValue value, TComparator compare)
{
	auto it = this->Begin();
	auto end = this->End();
	while (it != end)
	{
		if (compare(*it, value) == 0)
		{
			break;
		}
		++it;
	}
	return it;
}


template<typename TValue>
void Array<TValue>::Shrink()
{
	constexpr int NotImplemeted = -2;
	throw NotImplemeted;
}

template<typename TValue>
int Array<TValue>::Count()
{
	return this->count;
}



template<typename TValue>
Array<TValue>::ArrayIterator::ArrayIterator(TValue* pValue)
{
	this->pValue = pValue;
}

template<typename TValue>
typename Array<TValue>::ArrayIterator& Array<TValue>::ArrayIterator::operator++() noexcept
{
	++this->pValue;
	return *this;
}

template<typename TValue>
typename Array<TValue>::ArrayIterator& Array<TValue>::ArrayIterator::operator--() noexcept
{
	--this->pValue;
	return *this;
}

template<typename TValue>
typename Array<TValue>::ArrayIterator Array<TValue>::ArrayIterator::operator+(int offset) noexcept
{
	return ArrayIterator(this->pValue + offset);
}

template<typename TValue>
typename Array<TValue>::ArrayIterator Array<TValue>::ArrayIterator::operator-(int offset) noexcept
{
	return ArrayIterator(this->pValue - offset);
}

template<typename TValue>
bool Array<TValue>::ArrayIterator::operator==(const ArrayIterator& other) const noexcept
{
	return this->pValue == other.pValue;
}

template<typename TValue>
bool Array<TValue>::ArrayIterator::operator!=(const ArrayIterator& other) const noexcept
{
	return this->pValue != other.pValue;
}

template<typename TValue>
TValue& Array<TValue>::ArrayIterator::operator*()
{
	return *this->pValue;
}

template<typename TValue>
TValue* Array<TValue>::ArrayIterator::operator->()
{
	return this->pValue;
}

template<typename TValue>
Array<TValue>::ArrayIterator::operator ReversedArrayIterator()
{
	return ReversedArrayIterator(*this);
}

template<typename TValue>
Array<TValue>::ArrayIterator::ArrayIterator(ReversedArrayIterator& rIt)
{
	this->pValue = ((ArrayIterator)rIt).pValue;
}

#endif // !ARRAY

